package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 * 给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。
 * 可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。
 * 返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。
 * 岛屿 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-islands-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2021/12/14 09:47
 */
public class Solution_numIslands2_305 {

    public static void main(String[] args) {
        int m = 3, n = 3;
        int[][] positions = {{0, 0}, {0, 1}, {1, 2}, {2, 1}, {1, 1}};
        System.out.println(numIslands2(m, n, positions));
    }

    public static List<Integer> numIslands2(int m, int n, int[][] positions) {
        if (positions == null || positions.length == 0) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        UnionFind unionFind = new UnionFind(m, n);
        for (int i = 0; i < positions.length; i++) {
            list.add(unionFind.union(positions[i][0], positions[i][1]));
        }
        return list;
    }

    private static class UnionFind {

        private int row;
        private int col;
        // 岛屿个数
        private int islandCont;
        // 存放元素对应的值，默认是0，岛屿就是1
        private int[] arr;
        /**
         * 元素对应的父节点，
         * eg.parent[0]=3;parent[1]=3
         * 说明下标为0，1的父节点都是3
         */
        private int[] parent;
        /**
         * 当前父节点在内的元素个数
         * eg.parent[0]=3;parent[1]=3
         * 则parent[3]=2;
         */
        private int[] eleSize;

        public UnionFind(int m, int n) {
            row = m;
            col = n;
            int N = m * n;
            islandCont = 0;
            arr = new int[N];
            eleSize = new int[N];
            parent = new int[N];
        }

        /**
         * 思路：
         * 坐标（r,c）确定一个点
         *
         * @param r
         * @param c
         * @return
         */
        public int union(int r, int c) {
            int index = realIndex(r, c);
            if (arr[index] == 0) {
                // 等于0，说明未被初始化，第一次进来
                islandCont++;
                // 修改数组中元素为1
                arr[index] = 1;
                // 自己就是自己的父节点
                parent[index] = index;
                // 当前只有自己一个节点
                eleSize[index] = 1;
                // 向上
                process(index, r - 1, c);
                // 向下
                process(index, r + 1, c);
                // 向左
                process(index, r, c - 1);
                // 向右
                process(index, r, c + 1);
            }
            return islandCont;
        }

        private void process(int curIndex, int r2, int c2) {
            // 遍历处理
            if (r2 < 0 || r2 >= row || c2 < 0 || c2 >= col) {
                return;
            }
            int index2 = realIndex(r2, c2);
            if (arr[curIndex] == 0 || arr[index2] == 0) {
                return;
            }
            int curFather = findFather(curIndex);
            int nextFather = findFather(index2);
            if (curFather != nextFather) {
                /**
                 * 谁长就拼接在谁的下面
                 */
                int size1 = eleSize[curFather];
                int size2 = eleSize[nextFather];
                if (size1 >= size2) {
                    parent[nextFather] = curFather;
                    eleSize[curFather] = size1 + size2;
                    eleSize[nextFather] = 0;
                } else {
                    parent[curFather] = nextFather;
                    eleSize[nextFather] = size1 + size2;
                    eleSize[curFather] = 0;
                }
                // 合并依次，岛屿个数减1
                islandCont--;
            }
        }

        private int findFather(int index) {
            while (index != parent[index]) {
                index = parent[index];
            }
            return index;
        }

        private int realIndex(int m, int n) {
            return m * col + n;
        }

    }

}
